package map_set.leetcode.easy;

import java.util.HashMap;
import java.util.Map;

/**
 * @author bruin_du
 * @description 最长不含重复字符的子字符串
 * @date 2022/5/26 14:50
 **/
public class Offer48_LengthOfLongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        //方法一：使用map + 动态规划
//        mapAndDP(s);

        //方法二：使用数组+动态规划
        return arrayAndDP(s);
    }

    private static int arrayAndDP(String s) {
        if(s == null || s.length() == 0) return 0;
        if(s.length() == 1) return 1;
        int[] arr = new int[256];
        int maxLength = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            if(arr[index] != 0)
                //如果有相同元素,并且改下标在start之前,表明在改下表之后已经有重复字符了
                //所以start就不能从该下标开始,要取两者的最大值
                start = Math.max(start,arr[index]);
            //这里用了0判断是否存过字符，并且i是从0开始
            //所以就不能存储i,因为i可能为0
            arr[index] = i + 1;
            maxLength = Math.max(maxLength,i - start + 1);
        }
        return maxLength;
    }

    private static int mapAndDP(String s) {
        if(s == null || s.length() == 0) return 0;
        if(s.length() == 1) return 1;
        Map<Character,Integer> map = new HashMap<>();
        int retLength = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(map.containsKey(ch))
                start = Math.max(start,map.get(ch) + 1);
            map.put(ch,i);
            retLength = Math.max(retLength,i - start + 1);
        }
        return retLength;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
    }
}
